package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//单链表的选择排序：每次拿到链表最小节点前一个节点。剔除最小节点，放到新的链表后，最小节点前一个节点连接最小节点后一个节点。
public class SelectionSortLinkedList {

    static class Node{
        private int value;
        private Node node;

        public Node(int value,Node node){
            this.value = value;
            this.node = node;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node){
            this.node = node;
        }
    }

    public void selectionSortLinkedList(Node head){
        Node node = head;
        Node smallest = null;
        Node smallPre = null;
        Node tail = null;
        while(node != null){
            smallPre = getSmallestNodePre(node);
            if(smallPre != null){
                smallest = smallPre.getNode();
                smallPre.setNode(smallest.getNode());
            }else{
                smallest = node;
            }
            if(tail == null){
                head = smallest;
            }else{
                tail.setNode(smallest);
            }
            tail = smallest;
            node = smallPre == null ? node.getNode() : node;
        }
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.getValue()).append(" ");
            head = head.getNode();
        }
        System.out.print(sb);
    }

    private Node getSmallestNodePre(Node head){
        Node smallPre = null;
        Node small = head;
        Node pre = head;
        head = head.getNode();
        while(head != null){
            if(head.getValue() < small.getValue()){
                small = head;
                smallPre = pre;
            }
            pre = head;
            head = head.getNode();
        }
        return smallPre;
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        String[] numbers = scanner.readLine().split(" ");
        Node node = null;
        for(int i = len - 1;i >= 0;i--){
            node = new Node(Integer.parseInt(numbers[i]),node);
        }
        new SelectionSortLinkedList().selectionSortLinkedList(node);
    }
}
